/*
 * Copyright (C), 2015-2018
 * FileName: Solution086
 * Author:   zhao
 * Date:     2018/12/22 18:27
 * Description: 86. 分隔链表
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import com.lizhaoblog.diynode.ListNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈86. 分隔链表〉
 *
 * @author zhao
 * @date 2018/12/22 18:27
 * @since 1.0.1
 */
public class Solution086 {
    /**************************************
     * 题目
     给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

     你应当保留两个分区中每个节点的初始相对位置。

     示例:

     输入: head = 1->4->3->2->5->2, x = 3
     输出: 1->2->2->4->3->5
     **************************************/

    /*************************************
     想法：
     1. 搞2个指针，第一个指针表示达标的最后一个值，第二个值用来遍历整条链表，遍历完也结束了
     第一个指针表示达标的最后一个值：index1的前面的值都要小于x
     2. 使用2个链表，后面拼起来，在better方法里面

     我的做法
     超过80%的测试案例
     时间复杂度/空间复杂度：n/1
     代码执行过程：

     总结：

     ************************************/
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }

        ListNode result = head;
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode preNode = head;

        while (fast != null) {
            if (fast.val < x) {
                if (result.val >= x) {
                    preNode.next = fast.next;
                    fast.next = result;
                    result = fast;
                    fast = preNode.next;
                    slow = result;
                    continue;
                }

                if (slow.next.equals(fast)) {
                    preNode = fast;
                    fast = fast.next;
                    slow = slow.next;
                } else {
                    preNode.next = fast.next;
                    fast.next = slow.next;
                    slow.next = fast;
                    // 前进
                    fast = preNode.next;
                    slow = slow.next;
                }

            } else {
                preNode = fast;
                fast = fast.next;
            }
        }
        return result;
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public ListNode better(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode head1 = new ListNode(0), cur1 = head1, head2 = new ListNode(1), cur2 = head2;
        while (head != null) {
            if (head.val >= x) {
                cur2.next = head;
                head = head.next;
                cur2 = cur2.next;
                cur2.next = null;
            } else {
                cur1.next = head;
                head = head.next;
                cur1 = cur1.next;
                cur1.next = null;
            }
        }
        cur1.next = head2.next;
        return head1.next;
    }
}
